package com.yangzhe.algorithm.c039;

// 含有嵌套的字符串解码
// 测试链接 : https://leetcode.cn/problems/decode-string/
public class Code02_DecodeString_LeetCode {
    public static int where;

    /**
     * 思路：嵌套的递归
     * 变量设计：
     * 1. cur：当前递归收集到的字符串
     * 2. where：全局变量，当前递归方法解析到的最后一个位置，方便让父级方法知道解析到哪里了
     * 3. num：当前递归方法解析到的数字
     * <p>
     * 递归流程 f(chars, i)：
     * 1. 遇到数字：num = num * 10 + (c - '0')
     * 2. 遇到字母：添加到cur
     * 3. 遇到[：进入子递归方法 f(chars, i + 1)，返回值 * num 添加到cur
     * 4. 遇到]或中止: 返回cur，并更新where的位置
     *
     * @param s
     * @return
     */
    public String decodeString(String s) {
        where = 0;
        return f(s, 0);
    }

    public String f(String s, int i) {
        StringBuilder sb = new StringBuilder();
        int num = 0;
        while (i < s.length()) {
            char c = s.charAt(i);
            if (c >= '0' && c <= '9') {
                // 数字
                num = num * 10 + (c - '0');
            } else if ((c >= 'a' && c <= 'z')
                    || (c >= 'A' && c <= 'Z')) {
                sb.append(c);
            } else if (c == '[') {
                String subString = f(s, i + 1);
                i = where;
                // 递归完成后，使用数字 倍数 字符串
                for (; num > 0; num--) {
                    sb.append(subString);
                }

            } else if (c == ']') {
                break;
            }
            i++;
        }
        where = i;

        return sb.toString();
    }

    public static void main(String[] args) {
        Code02_DecodeString_LeetCode decodeString = new Code02_DecodeString_LeetCode();
        System.out.println(decodeString.decodeString("3[a]2[bc]"));
    }
}
